package 简单.贪心思想;

import java.util.Arrays;

/**
 * 请你将一些箱子装在 一辆卡车 上。给你一个二维数组 boxTypes ，
 * 其中 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：
 * numberOfBoxesi 是类型 i 的箱子的数量。
 * numberOfUnitsPerBoxi 是类型 i 每个箱子可以装载的单元数量。
 * 整数 truckSize 表示卡车上可以装载 箱子 的 最大数量 。只要箱子
 * 数量不超过 truckSize ，你就可以选择任意箱子装到卡车上。
 * 返回卡车可以装载 单元 的 最大 总数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-units-on-a-truck
 */
public class 卡车上的最大单元数_1710 {

    public static void main(String[] args) {

        System.out.println(maximumUnits(new int[][]{{1, 3}, {2, 2}, {3, 1}}, 4));

    }

    /**
     * 排序+贪心
     * 优先选择装载的单元数量较多的箱子
     *
     * @param boxTypes
     * @param truckSize
     * @return
     */
    public static int maximumUnits(int[][] boxTypes, int truckSize) {
        int count = 0;
        Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]);

        int idx = 0, curSize = 0;
        while (idx < boxTypes.length) {
            int[] boxType = boxTypes[idx];
            if (curSize + boxType[0] >= truckSize) {
                return count + (truckSize - curSize) * boxType[1];
            } else {
                // 一次性选择当前类型的全部箱子
                count += boxType[0] * boxType[1];
                curSize += boxType[0];
            }
            idx++;
        }

        return count;
    }

}
